package com.leetcode.algorithm.y22.m08.w3;

import java.util.Arrays;

/**
 * 435. 无重叠区间
 * 
 * https://leetcode.cn/problems/non-overlapping-intervals/
 * 
 * @author jie.deng
 *
 */
class Question0435Solution01 {

	public int eraseOverlapIntervals(int[][] intervals) {
		// 动态规划
		int len = intervals.length;
		Arrays.sort(intervals, (arr1, arr2) -> (arr1[0] - arr2[0]));

		int[] dp = new int[len];
		// dp[i] 表示以intervals[i]结尾的无重叠区间的个数
		dp[0] = 1;
		int max = dp[0];

		for (int i = 1; i < len; i++) {
			dp[i] = 1;
			for (int j = i - 1; j >= 0; j--) {
				if (intervals[i][0] >= intervals[j][1]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
					if (dp[i] > max) {
						max = dp[i];
						break;
					}
				}
			}
		}

		return len - max;
	}

}